#include <vector>
#include <functional>
using namespace std;

template <class T>
struct Less{
  
  bool operator()(const T& l, const T& r) const{
    return l < r;
  }
};

template <class T>
struct Greater{
  bool operator()(const T& l, const T& r) const{
    return l > r;
  }
};

template<class T, class Container=vector<T>, class Compare = Less<T>>
class Priority_queue{
  Container _con;
  Compare _com;
public:
  Priority_queue(){}

  template<class InputIterator>
  Priority_queue(InputIterator first, InputIterator last)
  {
    while(first != last)
    {
      _con.push_back(*first);
      ++first;
    }

    for(int i = (_con.size()-2)/2; i>=0; --i)
    {
      adjust_down(i);
    }

  }

  void push(const T& val)
  {
    _con.push_back(val);
    adjust_up(_con.size()-1);
  }

  void adjust_up(size_t child)
  {
    size_t parent = (child-1)/2;
    while(child > 0)
    {
      //if(_con[child] > _con[parent])
      if(_com(_con[parent], _con[child]))
      {
        std::swap(_con[child], _con[parent]);
        child = parent;
        parent = (child-1)/2;
      }
      else
      {
        break;
      }
    }
  }

  void pop()
  {
    std::swap(_con[0], _con[_con.size()-1]);
    _con.pop_back();
    adjust_down(0);
  }

  void adjust_down(size_t parent)
  {
    size_t child = parent*2+1;
    while(child < _con.size())
    {
      if(child+1<_con.size() && _com(_con[child], _con[child+1]))
      {
        ++child;
      }
      if(_com(_con[parent], _con[child]))
      {
        std::swap(_con[child], _con[parent]);
        parent = child;
        child = parent*2+1;
      }
      else
      {
        break;
      }
    }
  }

  const T& top() const{
   return _con.front(); 
  }

  bool empty() const{
    return _con.empty();
  }

  size_t size() const{
    return _con.size();
  }
};


